package com.gitee.wsl.collections.trie

import com.gitee.wsl.collections.iterator.api.MutableMapEntry
import com.gitee.wsl.collections.iterator.api.OrderedMapIterator
import com.gitee.wsl.collections.map.api.SequencedMap
import com.gitee.wsl.collections.map.api.SortedMap
import com.gitee.wsl.collections.trie.analyzer.KeyAnalyzer
import kotlin.concurrent.Volatile
import kotlin.jvm.Transient
//
//interface TrieEntry<K, V> {
//    var key: K?
//    var value: V?
//}
//
//interface PatriciaTrieEntry<K,V>:TrieEntry<K,V>{
//    fun setKeyValue(key: K, value: V): V? {
//        val oldValue = this.value
//        this.key = key
//        this.value = value
//        return oldValue
//    }
//
//    var bitIndex: Int
//
//    /** The parent of this entry.  */
//    var parent: PatriciaTrieEntry<K, V>?
//
//    /** The left child of this entry.  */
//    var left: PatriciaTrieEntry<K, V>
//
//    /** The right child of this entry.  */
//    var right: PatriciaTrieEntry<K, V>?
//
//    /** The entry who uplinks to this entry.  */
//    var predecessor: PatriciaTrieEntry<K, V>
//
//    /**
//     * Whether the entry is storing a key.
//     * Only the root can potentially be empty, all other
//     * nodes must have a key.
//     *
//     * @return Whether the entry is storing a key
//     */
//    val isEmpty: Boolean
//        get() = key == null
//
//    /**
//     * Whether the left or right child is a loopback.
//     *
//     * @return Whether the left or right child is a loopback.
//     */
//    val isExternalNode: Boolean
//        get() = !this.isInternalNode
//
//    /**
//     * Tests that neither the left nor right child is a loopback.
//     *
//     * @return That neither the left nor right child is a loopback.
//     */
//    val isInternalNode: Boolean
//        get() = left !== this && right !== this
//
//    class Node<K,V>(override var key: K? = null,
//                    override var value: V? = null,
//                    override var bitIndex: Int = -1
//    ): PatriciaTrieEntry<K,V>{
//        override var left: PatriciaTrieEntry<K, V> = this
//
//        override var right: PatriciaTrieEntry<K, V>? = null
//
//        override var predecessor: PatriciaTrieEntry<K, V> = this
//
//        override var parent: PatriciaTrieEntry<K, V>? = null
//    }
//
//    companion object{
//        fun<K,V> root() = Node<K,V>()
//
//        fun<K,V> node(key: K? = null,
//                      value: V? = null,
//                      bitIndex: Int = -1) = Node(key, value, bitIndex)
//    }
//}
//
///**
// * This class implements the base PATRICIA algorithm and everything that
// * is related to the [Map] interface.
// *
// * @param <K> the type of the keys in this map
// * @param <V> the type of the values in this map
// * @since 4.0
//</V></K> */
//abstract class AbstractPatriciaTrie<K,V> : AbstractBitwiseTrie<K,V> {
//
//    /**
//     * A range view of the [org.apache.commons.collections4.Trie].
//     */
//    private abstract inner class AbstractRangeMap : AbstractMutableMap<K,V>(), SortedMap<K,V> {
//        /** The [.entrySet] view.  */
//        @Volatile
//        @Transient
//        private var entrySet: MutableSet<MutableMapEntry<K,V>>? = null
//
//        override val comparator: Comparator<K>
//            get() = this@AbstractPatriciaTrie.comparator
//
//
//        override fun reversed(): SequencedMap<K,V> {
//            TODO("Not yet implemented")
//        }
//
//         override fun containsKey(key: K): Boolean {
//            if (!inRange(key)) {
//                return false
//            }
//
//            return this@AbstractPatriciaTrie.containsKey(key)
//        }
//
//        /**
//         * Creates and returns an [.entrySet] view of the [AbstractRangeMap].
//         */
//        protected abstract fun createEntrySet(): MutableSet<MutableMapEntry<K,V>>
//
//        /**
//         * Creates and returns a sub-range view of the current [AbstractRangeMap].
//         */
//        protected abstract fun createRangeMap(
//            fromKey: K?, fromInclusive: Boolean,
//            toKey: K?, toInclusive: Boolean,
//        ): SortedMap<K,V>
//
//
//        override val entries: MutableSet<MutableMapEntry<K,V>>
//            get(){
//                if (entrySet == null) {
//                    entrySet = createEntrySet()
//                }
//                return entrySet!!
//            }
//
//
//         override fun get(key: K): V? {
//            if (!inRange(key)) {
//                return null
//            }
//
//            return this@AbstractPatriciaTrie[key]
//        }
//
//        /**
//         * Returns the FROM Key.
//         */
//         abstract val fromKey: K?
//
//        /**
//         * Returns the TO Key.
//         */
//         abstract val toKey: K?
//
//        override fun headMap(toKey: K): SortedMap<K,V> {
//            require(inRange2(toKey)) { "ToKey is out of range: $toKey" }
//            return createRangeMap(this.fromKey, this.isFromInclusive, toKey, this.isToInclusive)
//        }
//
//        /**
//         * Returns true if the provided key is in the FROM range of the [AbstractRangeMap].
//         */
//        protected open fun inFromRange(key: K, forceInclusive: Boolean): Boolean {
//            val fromKey = this.fromKey
//            val fromInclusive = this.isFromInclusive
//
//            val ret = keyAnalyzer.compare(key, fromKey)
//            if (fromInclusive || forceInclusive) {
//                return ret >= 0
//            }
//            return ret > 0
//        }
//
//        /**
//         * Returns true if the provided key is greater than TO and less than FROM.
//         */
//        open fun inRange(key: K): Boolean {
//            val fromKey = this.fromKey
//            val toKey = this.toKey
//
//            return (fromKey == null || inFromRange(key, false)) && (toKey == null || inToRange(key, false))
//        }
//
//        /**
//         * This form allows the high endpoint (as well as all legit keys).
//         */
//        protected open fun inRange2(key: K): Boolean {
//            val fromKey = this.fromKey
//            val toKey = this.toKey
//
//            return (fromKey == null || inFromRange(key, false)) && (toKey == null || inToRange(key, true))
//        }
//
//        /**
//         * Returns true if the provided key is in the TO range of the [AbstractRangeMap].
//         */
//        protected open fun inToRange(key: K, forceInclusive: Boolean): Boolean {
//            val toKey = this.toKey
//            val toInclusive = this.isToInclusive
//
//            val ret = keyAnalyzer.compare(key, toKey)
//            if (toInclusive || forceInclusive) {
//                return ret <= 0
//            }
//            return ret < 0
//        }
//
//        /**
//         * Whether or not the [.getFromKey] is in the range.
//         */
//        protected abstract val isFromInclusive: Boolean
//
//        /**
//         * Whether or not the [.getToKey] is in the range.
//         */
//        protected abstract val isToInclusive: Boolean
//
//         override fun put(key: K, value: V): V? {
//            require(inRange(key)) { "Key is out of range: $key" }
//            return this@AbstractPatriciaTrie.put(key, value)
//        }
//
//         override fun remove(key: K): V? {
//            if (!inRange(key)) {
//                return null
//            }
//
//            return this@AbstractPatriciaTrie.remove(key)
//        }
//
//        override fun subMap(fromKey: K, toKey: K): SortedMap<K,V> {
//            require(inRange2(fromKey)) { "FromKey is out of range: $fromKey" }
//
//            require(inRange2(toKey)) { "ToKey is out of range: $toKey" }
//
//            return createRangeMap(fromKey, this.isFromInclusive, toKey, this.isToInclusive)
//        }
//
//        override fun tailMap(fromKey: K): SortedMap<K,V> {
//            require(inRange2(fromKey)) { "FromKey is out of range: $fromKey" }
//            return createRangeMap(fromKey, this.isFromInclusive, this.toKey, this.isToInclusive)
//        }
//    }
//
//    /**
//     * An iterator for the entries.
//     */
//    internal abstract inner class AbstractTrieIterator<E> : MutableIterator<E> {
//        /** For fast-fail.  */
//        protected var expectedModCount: Int = this@AbstractPatriciaTrie.modCount
//
//        protected var next: PatriciaTrieEntry<K,V>? // the next node to return
//        protected var current: PatriciaTrieEntry<K,V>? = null // the current entry we're on
//
//        /**
//         * Starts iteration from the root.
//         */
//        protected constructor() {
//            next = this@AbstractPatriciaTrie.nextEntry(null)
//        }
//
//        /**
//         * Starts iteration at the given entry.
//         */
//        protected constructor(firstEntry: PatriciaTrieEntry<K,V>) {
//            next = firstEntry
//        }
//
//        /**
//         * @see PatriciaTrie.nextEntry
//         */
//        protected open fun findNext(prior: PatriciaTrieEntry<K,V>): PatriciaTrieEntry<K,V>? {
//            return this@AbstractPatriciaTrie.nextEntry(prior)
//        }
//
//         override fun hasNext(): Boolean {
//            return next != null
//        }
//
//        /**
//         * Returns the next [TrieEntry].
//         */
//        protected open fun nextEntry(): PatriciaTrieEntry<K,V> {
//            if (expectedModCount != this@AbstractPatriciaTrie.modCount) {
//                throw ConcurrentModificationException()
//            }
//
//            val e = next
//            if (e == null) {
//                throw NoSuchElementException()
//            }
//
//            next = findNext(e)
//            current = e
//            return e
//        }
//
//        override fun remove() {
//            checkNotNull(current)
//
//            if (expectedModCount != this@AbstractPatriciaTrie.modCount) {
//                throw ConcurrentModificationException()
//            }
//
//            val node = current
//            current = null
//            this@AbstractPatriciaTrie.removeEntry(node!!)
//
//            expectedModCount = this@AbstractPatriciaTrie.modCount
//        }
//    }
//
//    /**
//     * This is an entry set view of the [org.apache.commons.collections4.Trie] as returned by [Map.entrySet].
//     */
//    private inner class EntrySet : AbstractMutableSet<PatriciaTrieEntry<K,V>>() {
//        /**
//         * An [Iterator] that returns [Entry] Objects.
//         */
//        private inner class EntryIterator() : AbstractTrieIterator<PatriciaTrieEntry<K,V>>() {
//             override fun next(): PatriciaTrieEntry<K,V>{
//                return nextEntry()
//            }
//        }
//
//         override fun clear() {
//            this@AbstractPatriciaTrie.clear()
//        }
//
//         override fun contains(element: PatriciaTrieEntry<K,V>): Boolean {
////            if (o !is BasicEntry) {
////                return false
////            }
//
//            val candidate = getEntry(element.key)
//            return candidate != null && candidate == element
//        }
//
//         override fun iterator(): MutableIterator<PatriciaTrieEntry<K,V>> {
//            return EntryIterator()
//        }
//
//        override fun add(element: PatriciaTrieEntry<K,V>): Boolean {
//            TODO("Not yet implemented")
//        }
//
//         override fun remove(element: PatriciaTrieEntry<K,V>): Boolean {
////            if (obj !is BasicEntry) {
////                return false
////            }
//            if (!contains(element)) {
//                return false
//            }
//            //val entry = element as BasicEntry<*, *>
//            this@AbstractPatriciaTrie.remove(element.key)
//            return true
//        }
//
//        override val size: Int
//            get() = this@AbstractPatriciaTrie.size
//
//    }
//
//    /**
//     * This is a key set view of the [org.apache.commons.collections4.Trie] as returned by [Map.keySet].
//     */
//    private inner class KeySet : AbstractMutableSet<K>() {
//        /**
//         * An [Iterator] that returns Key Objects.
//         */
//        private inner class KeyIterator : AbstractTrieIterator<K>() {
//             override fun next(): K {
//                return nextEntry().key!!
//            }
//        }
//
//         override fun clear() {
//            this@AbstractPatriciaTrie.clear()
//        }
//
//         override fun contains(element: K): Boolean {
//            return containsKey(element)
//        }
//
//         override fun iterator(): MutableIterator<K> {
//            return KeyIterator()
//        }
//
//        override fun add(element: K): Boolean {
//            TODO("Not yet implemented")
//        }
//
//         override fun remove(element: K): Boolean {
//            val localSize = size
//            this@AbstractPatriciaTrie.remove(element)
//            return localSize != size
//        }
//
//        override val size: Int
//            get() = this@AbstractPatriciaTrie.size
//
//    }
//
//    /**
//     * A prefix [RangeEntrySet] view of the [org.apache.commons.collections4.Trie].
//     */
//    private inner class PrefixRangeEntrySet(
//        override val delegate: PrefixRangeMap
//    ) : RangeEntrySet(delegate) {
//        /**
//         * An [Iterator] for iterating over a prefix search.
//         */
//        private inner class EntryIterator(
//            // the subtree to search within
//            private var subtree: PatriciaTrieEntry<K,V>,
//            prefix: K?,
//            offset: Int,
//            lengthInBits: Int,
//        ) : AbstractTrieIterator<PatriciaTrieEntry<K,V>>() {
//            // values to reset the subtree if we remove it.
//            private val prefix: K?
//            private val offset: Int
//            private val lengthInBits: Int
//            private var lastOne = false
//
//            /**
//             * Starts iteration at the given entry &amp; search only
//             * within the given subtree.
//             */
//            init {
//                next = this@AbstractPatriciaTrie.followLeft(subtree)
//                this.prefix = prefix
//                this.offset = offset
//                this.lengthInBits = lengthInBits
//            }
//
//            override fun findNext(prior: PatriciaTrieEntry<K,V>): PatriciaTrieEntry<K,V>? {
//                return this@AbstractPatriciaTrie.nextEntryInSubtree(prior, subtree)
//            }
//
//             override fun next(): PatriciaTrieEntry<K,V> {
//                val entry = nextEntry()
//                if (lastOne) {
//                    next = null
//                }
//                return entry
//            }
//
//            override fun remove() {
//                // If the current entry we're removing is the subtree
//                // then we need to find a new subtree parent.
//                var needsFixing = false
//                val bitIdx = subtree.bitIndex
//                if (current == subtree) {
//                    needsFixing = true
//                }
//
//                super.remove()
//
//                // If the subtree changed its bitIndex or we
//                // removed the old subtree, get a new one.
//                if (bitIdx != subtree.bitIndex || needsFixing) {
//                    subtree = subtree(prefix, offset, lengthInBits)!!
//                }
//
//                // If the subtree's bitIndex is less than the
//                // length of our prefix, it's the last item
//                // in the prefix tree.
//                if (lengthInBits >= subtree.bitIndex) {
//                    lastOne = true
//                }
//            }
//        }
//
//        /**
//         * An [Iterator] that holds a single [TrieEntry].
//         */
//        private inner class SingletonIterator(
//               private val entry: PatriciaTrieEntry<K,V>
//          ) : MutableIterator<PatriciaTrieEntry<K,V>> {
//            private var hit = 0
//
//             override fun hasNext(): Boolean {
//                return hit == 0
//            }
//
//             override fun next(): PatriciaTrieEntry<K,V> {
//                if (hit != 0) {
//                    throw NoSuchElementException()
//                }
//
//                ++hit
//                return entry
//            }
//
//             override fun remove() {
//                check(hit == 1)
//
//                ++hit
//                this@AbstractPatriciaTrie.removeEntry(entry)
//            }
//        }
//
//        private var prefixStart: PatriciaTrieEntry<K,V>? = null
//
//        private var expectedModCount = 0
//
//        override fun iterator(): MutableIterator<PatriciaTrieEntry<K,V>> {
//            if (this@AbstractPatriciaTrie.modCount != expectedModCount) {
//                prefixStart = subtree(delegate.prefix, delegate.offsetInBits, delegate.lengthInBits)
//                expectedModCount = this@AbstractPatriciaTrie.modCount
//            }
//
//            if (prefixStart == null) {
//                val empty = mutableSetOf<TrieEntry<K,V>>()
//                return empty.iterator()
//            }
//            if (delegate.lengthInBits > prefixStart!!.bitIndex) {
//                return SingletonIterator(prefixStart!!)
//            }
//            return EntryIterator(
//                prefixStart!!,
//                delegate.prefix,
//                delegate.offsetInBits,
//                delegate.lengthInBits
//            )
//        }
//
//        override val size: Int
//            get() = delegate.fixup()
//
//    }
//
//    /**
//     * A submap used for prefix views over the [org.apache.commons.collections4.Trie].
//     */
//    private inner class PrefixRangeMap(
//        val prefix: K?,
//        val offsetInBits: Int,
//        val lengthInBits: Int
//    ) : AbstractRangeMap() {
//        override var fromKey: K? = null
//            private set
//
//        override var toKey: K? = null
//            private set
//
//        @Transient
//        private var expectedModCount = 0
//
//        override var size = -1
//
//         override fun clear() {
//            val it = this@AbstractPatriciaTrie.entries.iterator()
//            val currentKeys = keys
//            while (it.hasNext()) {
//                if (currentKeys.contains(it.next().key)) {
//                    it.remove()
//                }
//            }
//        }
//
//        override fun createEntrySet(): MutableSet<MutableMapEntry<K,V>> {
//            return PrefixRangeEntrySet(this) as MutableSet<MutableMapEntry<K,V>>
//        }
//
//        override fun createRangeMap(
//            fromKey: K?, fromInclusive: Boolean,
//            toKey: K?, toInclusive: Boolean,
//        ): SortedMap<K,V> {
//            return RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive)
//        }
//
//        override fun firstKey(): K? {
//            fixup()
//            var e: MutableMapEntry<K,V>? = null
//            if (fromKey == null) {
//                e = firstEntry()
//            } else {
//                e = higherEntry(fromKey!!)
//            }
//
//            val first = e?.key
//            if (e == null || !keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, first!!)) {
//                throw NoSuchElementException()
//            }
//
//            return first
//        }
//
//        /**
//         * This method does two things. It determines the FROM
//         * and TO range of the [PrefixRangeMap] and the number
//         * of elements in the range. This method must be called every
//         * time the [org.apache.commons.collections4.Trie] has changed.
//         */
//        fun fixup(): Int {
//            // The trie has changed since we last found our toKey / fromKey
//            if (size == -1 || this@AbstractPatriciaTrie.modCount != expectedModCount) {
//                val it = super.entries.iterator()
//                size = 0
//
//                var entry: MutableMapEntry<K,V>? = null
//                if (it.hasNext()) {
//                    entry = it.next()
//                    size = 1
//                }
//
//                fromKey = entry?.key
//                if (fromKey != null) {
//                    val prior = previousEntry(entry as TrieEntry<K,V>)
//                    fromKey = prior?.key
//                }
//
//                toKey = fromKey
//
//                while (it.hasNext()) {
//                    ++size
//                    entry = it.next()
//                }
//
//                toKey = entry?.key
//
//                if (toKey != null) {
//                    entry = nextEntry(entry)
//                    toKey = entry?.key
//                }
//
//                expectedModCount = this@AbstractPatriciaTrie.modCount
//            }
//
//            return size
//        }
//
//        /**
//         * Returns true if the provided Key is in the FROM range of the [PrefixRangeMap].
//         */
//        override fun inFromRange(key: K, forceInclusive: Boolean): Boolean {
//            return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key)
//        }
//
//        /**
//         * Returns true if this [PrefixRangeMap]'s key is a prefix of the provided key.
//         */
//        override fun inRange(key: K): Boolean {
//            return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key)
//        }
//
//        /**
//         * Same as [.inRange].
//         */
//        override fun inRange2(key: K): Boolean {
//            return inRange(key)
//        }
//
//        /**
//         * Returns true if the provided Key is in the TO range of the [PrefixRangeMap].
//         */
//        override fun inToRange(key: K, forceInclusive: Boolean): Boolean {
//            return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key)
//        }
//
//        override val isFromInclusive: Boolean
//            get() = false
//
//        override val isToInclusive: Boolean
//            get() = false
//
//        override fun lastKey(): K {
//            fixup()
//
//            var e: MutableMapEntry<K,V>? = null
//            e = if (toKey == null) {
//                lastEntry()
//            } else {
//                lowerEntry(toKey!!)
//            }
//
//            val last = e?.key
//            if (e == null || !keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, last!!)) {
//                throw NoSuchElementException()
//            }
//
//            return last
//        }
//    }
//
//    /**
//     * A [AbstractRangeMap] that deals with [Entry]s.
//     */
//    private inner class RangeEntryMap(
//        override val fromKey: K?,
//        override val isFromInclusive: Boolean,
//        override val toKey: K?,
//        override val isToInclusive: Boolean
//    ) : AbstractRangeMap() {
//        /** The key to start from, null if the beginning.  */
//        //override val fromKey: K
//
//        /** The key to end at, null if till the end.  */
//        //override val toKey: K
//
//        /** Whether or not the 'from' is inclusive.  */
//        //override val isFromInclusive: Boolean
//
//        /** Whether or not the 'to' is inclusive.  */
//        //override val isToInclusive: Boolean
//
//        /**
//         * Creates a [RangeEntryMap].
//         */
//        init {
//            require(!(fromKey == null && toKey == null)) { "must have a from or to!" }
//
//            require(!(fromKey != null && toKey != null && keyAnalyzer.compare(fromKey, toKey) > 0)) { "fromKey > toKey" }
//
////            this.fromKey = fromKey
////            this.isFromInclusive = fromInclusive
////            this.toKey = toKey
////            this.isToInclusive = toInclusive
//        }
//
//        /**
//         * Creates a [RangeEntryMap] with the fromKey included and
//         * the toKey excluded from the range.
//         */
//        constructor(
//            fromKey: K?,
//            toKey: K?
//        ) : this(fromKey, true, toKey, false)
//
//        override fun createEntrySet(): MutableSet<MutableMapEntry<K,V>> {
//            return RangeEntrySet(this) as MutableSet<MutableMapEntry<K,V>>
//        }
//
//        override fun createRangeMap(
//            fromKey: K?, fromInclusive: Boolean,
//            toKey: K?, toInclusive: Boolean,
//        ): SortedMap<K,V> {
//            return RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive)
//        }
//
//        override fun firstKey(): K? {
//            var e: MutableMapEntry<K,V>? = null
//            e = if (fromKey == null) {
//                firstEntry()
//            } else if (this.isFromInclusive) {
//                ceilingEntry(fromKey)
//            } else {
//                higherEntry(fromKey)
//            }
//
//            val first = e?.key
//            if (e == null || toKey != null && !inToRange(first!!, false)) {
//                throw NoSuchElementException()
//            }
//            return first
//        }
//
//        override fun lastKey(): K? {
//            val e = if (toKey == null) {
//                lastEntry()
//            } else if (this.isToInclusive) {
//                floorEntry(toKey)
//            } else {
//                lowerEntry(toKey)
//            }
//
//            val last = e?.key
//            if (e == null || fromKey != null && !inFromRange(last!!, false)) {
//                throw NoSuchElementException()
//            }
//            return last
//        }
//    }
//
//    /**
//     * A [Set] view of a [AbstractRangeMap].
//     */
//    private open inner class RangeEntrySet(
//        open val delegate: AbstractRangeMap
//    ) : AbstractMutableSet<MutableMapEntry<K,V>>() {
//        /**
//         * An [Iterator] for [RangeEntrySet]s.
//         */
//        private inner class EntryIterator(
//            first: TrieEntry<K,V>,
//            last: TrieEntry<K,V>?
//        ) : AbstractTrieIterator<MutableMapEntry<K,V>>(first) {
//            private val excludedKey: K? = last?.key
//
//            override fun hasNext(): Boolean {
//                return next != null && !compare(next!!.key, excludedKey)
//            }
//
//             override fun next(): MutableMapEntry<K,V> {
//                if (next == null || compare(next!!.key, excludedKey)) {
//                    throw NoSuchElementException()
//                }
//                return nextEntry()
//            }
//        }
//
//        //private val delegate: AbstractRangeMap = Objects.requireNonNull(delegate, "delegate")
//
//        @Transient
//        private var _size = -1
//
//        @Transient
//        private var expectedModCount = 0
//
//         override fun contains(element: MutableMapEntry<K,V>): Boolean {
////            if (o !is MutableMapEntry) {
////                return false
////            }
//
//            val entry = element
//            val key = entry.key!!
//            if (!delegate.inRange(key)) {
//                return false
//            }
//
//            val node = getEntry(key)
//            return node != null && compare(node.value, entry.value)
//        }
//
//         override fun isEmpty(): Boolean {
//            return !iterator().hasNext()
//        }
//
//         override fun iterator(): MutableIterator<MutableMapEntry<K,V>> {
//            val fromKey = delegate.fromKey
//            val toKey = delegate.toKey
//            val first: TrieEntry<K,V>? = if (fromKey == null) {
//                firstEntry()
//            } else {
//                ceilingEntry(fromKey)
//            }
//
//            var last: TrieEntry<K,V>? = null
//            if (toKey != null) {
//                last = ceilingEntry(toKey)
//            }
//
//            return EntryIterator(first!!, last)
//        }
//
//        override fun add(element: MutableMapEntry<K,V>): Boolean {
//            TODO("Not yet implemented")
//        }
//
//         override fun remove(element: MutableMapEntry<K,V>): Boolean {
////            if (o !is BasicEntry) {
////                return false
////            }
//
//            val entry = element
//            val key: K = entry.key!!
//            if (!delegate.inRange(key)) {
//                return false
//            }
//
//            val node = getEntry(key)
//            if (node != null && compare(node.value, entry.value)) {
//                removeEntry(node)
//                return true
//            }
//            return false
//        }
//
//        override val size: Int
//            get() {
//                if (_size == -1 || expectedModCount != this@AbstractPatriciaTrie.modCount) {
//                    _size = 0
//
//                    val it: Iterator<*> = iterator()
//                    while (it.hasNext()) {
//                        ++_size
//                        it.next()
//                    }
//
//                    expectedModCount = this@AbstractPatriciaTrie.modCount
//                }
//                return _size
//            }
//
//    }
//
//    /**
//     * A [Reference] allows us to return something through a Method's
//     * argument list. An alternative would be to an Array with a length of
//     * one (1) but that leads to compiler warnings. Computationally and memory
//     * wise there's no difference (except for the need to load the
//     * [Reference] Class but that happens only once).
//     */
//    private class Reference<E> {
//        private var item: E? = null
//
//        fun get(): E? {
//            return item
//        }
//
//        fun set(item: E?) {
//            this.item = item
//        }
//    }
//
//    /**
//     * A [org.apache.commons.collections4.Trie] is a set of [TrieEntry] nodes.
//     *
//     * @param <K> the key type.
//     * @param <V> the value type.
//    </V></K> */
//    class TrieEntry<K,V>(
//        key: K,
//        value: V,
//        /** The index this entry is comparing.  */
//        override var bitIndex: Int,
//    ) : BasicEntry<K,V>(key, value),PatriciaTrieEntry<K,V> {
//        /** The parent of this entry.  */
//        override var parent: PatriciaTrieEntry<K, V>? = null
//
//        /** The left child of this entry.  */
//        override var left: PatriciaTrieEntry<K, V> = this
//
//        /** The right child of this entry.  */
//        override var right: PatriciaTrieEntry<K, V>? = null
//
//        /** The entry who uplinks to this entry.  */
//        override var predecessor: PatriciaTrieEntry<K, V> = this
//
//        override fun setKeyValue(key: K, value: V): V {
//            val oldValue = this.value
//            this.key = key
//            this.value = value
//            return oldValue
//        }
//
//         override fun toString(): String {
//            val buffer = StringBuilder()
//
//            if (bitIndex == -1) {
//                buffer.append("RootEntry(")
//            } else {
//                buffer.append("Entry(")
//            }
//
//            buffer.append("key=").append(key).append(" [").append(bitIndex).append("], ")
//            buffer.append("value=").append(value).append(", ")
//
//            //buffer.append("bitIndex=").append(bitIndex).append(", ");
//            if (parent != null) {
//                if (parent!!.bitIndex == -1) {
//                    buffer.append("parent=").append("ROOT")
//                } else {
//                    buffer.append("parent=").append(parent!!.key).append(" [").append(parent!!.bitIndex).append("]")
//                }
//            } else {
//                buffer.append("parent=").append("null")
//            }
//            buffer.append(", ")
//
//            if (left != null) {
//                if (left!!.bitIndex == -1) {
//                    buffer.append("left=").append("ROOT")
//                } else {
//                    buffer.append("left=").append(left!!.key).append(" [").append(left!!.bitIndex).append("]")
//                }
//            } else {
//                buffer.append("left=").append("null")
//            }
//            buffer.append(", ")
//
//            if (right != null) {
//                if (right!!.bitIndex == -1) {
//                    buffer.append("right=").append("ROOT")
//                } else {
//                    buffer.append("right=").append(right!!.key).append(" [").append(right!!.bitIndex).append("]")
//                }
//            } else {
//                buffer.append("right=").append("null")
//            }
//            buffer.append(", ")
//
//            if (predecessor != null) {
//                if (predecessor!!.bitIndex == -1) {
//                    buffer.append("predecessor=").append("ROOT")
//                } else {
//                    buffer.append("predecessor=").append(predecessor!!.key).append(" [").append(predecessor!!.bitIndex).append("]")
//                }
//            }
//
//            buffer.append(")")
//            return buffer.toString()
//        }
//
//    }
//
//    /**
//     * An [OrderedMapIterator] for a [org.apache.commons.collections4.Trie].
//     */
//    private inner class TrieMapIterator : AbstractTrieIterator<K>(), OrderedMapIterator<K,V> {
//        protected var previous: PatriciaTrieEntry<K,V>? = null // the previous node to return
//
//        override fun getKey(): K {
//            checkNotNull(current)
//            return current!!.key!!
//        }
//
//        override fun getValue(): V {
//            checkNotNull(current)
//            return current!!.value!!
//        }
//
//        override fun hasPrevious(): Boolean {
//            return previous != null
//        }
//
//        override fun next(): K {
//            return nextEntry().key!!
//        }
//
//        override fun nextEntry(): PatriciaTrieEntry<K,V> {
//            val nextEntry = super.nextEntry()
//            previous = nextEntry
//            return nextEntry
//        }
//
//        override fun previous(): K {
//            return previousEntry().key!!
//        }
//
//        protected fun previousEntry(): PatriciaTrieEntry<K,V> {
//            if (expectedModCount != this@AbstractPatriciaTrie.modCount) {
//                throw ConcurrentModificationException()
//            }
//
//            val e = previous
//            if (e == null) {
//                throw NoSuchElementException()
//            }
//
//            previous = this@AbstractPatriciaTrie.previousEntry(e)
//            next = current
//            current = e
//            return current!!
//        }
//
//        override fun setValue(value: V): V {
//            checkNotNull(current)
//            return current!!.setValue(value)
//        }
//    }
//
//    /**
//     * This is a value view of the [org.apache.commons.collections4.Trie] as returned by [Map.values].
//     */
//    private inner class Values : AbstractMutableCollection<V>() {
//        /**
//         * An [Iterator] that returns Value Objects.
//         */
//        private inner class ValueIterator : AbstractTrieIterator<V>() {
//             override fun next(): V {
//                return nextEntry().value!!
//            }
//        }
//
//         override fun clear() {
//            this@AbstractPatriciaTrie.clear()
//        }
//
//         override fun contains(element: V): Boolean {
//            return containsValue(element)
//        }
//
//         override fun iterator(): MutableIterator<V> {
//            return ValueIterator()
//        }
//
//        override fun add(element: V): Boolean {
//            TODO("Not yet implemented")
//        }
//
//         override fun remove(element: V): Boolean {
//            val it = iterator()
//            while (it.hasNext()) {
//                val value = it.next()
//                if (compare(value, element)) {
//                    it.remove()
//                    return true
//                }
//            }
//            return false
//        }
//
//        override val size: Int
//            get() = this@AbstractPatriciaTrie.size
//
//    }
//
//    /** The root node of the [org.apache.commons.collections4.Trie].  */
//    @Transient
//    private var root:PatriciaTrieEntry<K,V> = PatriciaTrieEntry.root()
//
//    /**
//     * Each of these fields are initialized to contain an instance of the
//     * appropriate view the first time this view is requested. The views are
//     * stateless, so there's no reason to create more than one of each.
//     */
//    @Volatile
//    @Transient
//    private var _keySet: MutableSet<K>? = null
//
//    @Volatile
//    @Transient
//    private var _values: MutableCollection<V>? = null
//
//    @Volatile
//    @Transient
//    private var _entrySet: MutableSet<MutableMap.MutableEntry<K,V>>? = null
//
//    /** The current size of the [org.apache.commons.collections4.Trie].  */
//    @Transient
//    override var size = 0
//
//    /**
//     * The number of times this [org.apache.commons.collections4.Trie] has been modified.
//     * It's used to detect concurrent modifications and fail-fast the [Iterator]s.
//     */
//    @Transient
//    protected var modCount: Int = 0
//
//    /**
//     * Constructs a new [Trie] using the given [KeyAnalyzer].
//     *
//     * @param keyAnalyzer  the [KeyAnalyzer].
//     */
//    protected constructor(keyAnalyzer: KeyAnalyzer<K>) : super(keyAnalyzer)
//
//    /**
//     * Constructs a new [org.apache.commons.collections4.Trie] using the given [KeyAnalyzer] and initializes the
//     * [org.apache.commons.collections4.Trie] with the values from the provided [Map].
//     *
//     * @param keyAnalyzer  the [KeyAnalyzer].
//     * @param map The source map.
//     */
//    protected constructor(keyAnalyzer: KeyAnalyzer<K>, map: Map<K,V>) : super(keyAnalyzer) {
//        putAll(map)
//    }
//
//    /**
//     * Adds the given [TrieEntry] to the [org.apache.commons.collections4.Trie].
//     */
//    fun addEntry(entry: PatriciaTrieEntry<K,V>, lengthInBits: Int): PatriciaTrieEntry<K,V> {
//        var current = root.left
//        var path = root
//        while (true) {
//            if (current.bitIndex >= entry.bitIndex || current.bitIndex <= path.bitIndex) {
//                entry.predecessor = entry
//
//                if (!isBitSet(entry.key, entry.bitIndex, lengthInBits)) {
//                    entry.left = entry
//                    entry.right = current
//                } else {
//                    entry.left = current
//                    entry.right = entry
//                }
//
//                entry.parent = path
//                if (current.bitIndex >= entry.bitIndex) {
//                    current.parent = entry
//                }
//
//                // if we inserted an uplink, set the predecessor on it
//                if (current.bitIndex <= path.bitIndex) {
//                    current.predecessor = entry
//                }
//
//                if (path === root || !isBitSet(entry.key, path.bitIndex, lengthInBits)) {
//                    path.left = entry
//                } else {
//                    path.right = entry
//                }
//
//                return entry
//            }
//
//            path = current
//
//            current = if (!isBitSet(entry.key, current.bitIndex, lengthInBits)) {
//                current.left
//            } else {
//                current.right!!
//            }
//        }
//    }
//
//    /**
//     * Returns a key-value mapping associated with the least key greater
//     * than or equal to the given key, or null if there is no such key.
//     */
//    fun ceilingEntry(key: K): PatriciaTrieEntry<K,V>? {
//        // Basically:
//        // Follow the steps of adding an entry, but instead...
//        //
//        // - If we ever encounter a situation where we found an equal
//        //   key, we return it immediately.
//        //
//        // - If we hit an empty root, return the first iterable item.
//        //
//        // - If we have to add a new item, we temporarily add it,
//        //   find the successor to it, then remove the added item.
//        //
//        // These steps ensure that the returned value is either the
//        // entry for the key itself, or the first entry directly after
//        // the key.
//
//        // TODO: Cleanup so that we don't actually have to add/remove from the
//        //       tree.  (We do it here because there are other well-defined
//        //       functions to perform the search.)
//
//        val lengthInBits = lengthInBits(key)
//
//        if (lengthInBits == 0) {
//            if (!root.isEmpty) {
//                return root
//            }
//            return firstEntry()
//        }
//
//        val found = getNearestEntryForKey(key, lengthInBits)
//        if (compareKeys(key, found.key)) {
//            return found
//        }
//
//        val bitIndex = bitIndex(key, found.key)
//        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
//            val added = PatriciaTrieEntry<K,V>.node(key, null, bitIndex)
//            addEntry(added, lengthInBits)
//            incrementSize() // must increment because remove will decrement
//            val ceil = nextEntry(added)
//            removeEntry(added)
//            modCount -= 2 // we didn't really modify it.
//            return ceil
//        }
//        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
//            if (!root.isEmpty) {
//                return root
//            }
//            return firstEntry()
//        }
//        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
//            return found
//        }
//
//        // we should have exited above.
//        throw IllegalStateException("invalid lookup: $key")
//    }
//
//     override fun clear() {
//        root.key = null
//        root.bitIndex = -1
//        root.value = null
//
//        root.parent = null
//        root.left = root
//        root.right = null
//        root.predecessor = root
//
//        size = 0
//        incrementModCount()
//    }
//
//    override val comparator: Comparator<K>
//        get() = keyAnalyzer
//
//
//     override fun containsKey(key: K): Boolean {
//        if (key == null) {
//            return false
//        }
//
//        val key: K = key
//        val lengthInBits = lengthInBits(key)
//        val entry = getNearestEntryForKey(key, lengthInBits)
//        return !entry.isEmpty && compareKeys(key, entry.key)
//    }
//
//    /**
//     * A helper method to decrement the [org.apache.commons.collections4.Trie] size and increment the modification counter.
//     */
//    fun decrementSize() {
//        size--
//        incrementModCount()
//    }
//
//
//    override val entries: MutableSet<MutableMap.MutableEntry<K,V>>
//        get() {
//            if (_entrySet == null) {
//                _entrySet = EntrySet() as MutableSet<MutableMap.MutableEntry<K,V>>
//            }
//            return _entrySet!!
//        }
//
//    /**
//     * Returns the first entry the [org.apache.commons.collections4.Trie] is storing.
//     *
//     *
//     * This is implemented by going always to the left until
//     * we encounter a valid uplink. That uplink is the first key.
//     */
//     override fun firstEntry(): PatriciaTrieEntry<K,V>? {
//        // if Trie is empty, no first node.
//        if (isEmpty()) {
//            return null
//        }
//        return followLeft(root)
//    }
//
//    override fun firstKey(): K {
//        if (isEmpty()) {
//            throw NoSuchElementException()
//        }
//        return firstEntry().key
//    }
//
//    /**
//     * Returns a key-value mapping associated with the greatest key
//     * less than or equal to the given key, or null if there is no such key.
//     */
//    fun floorEntry(key: K): PatriciaTrieEntry<K,V>? {
//        // TODO: Cleanup so that we don't actually have to add/remove from the
//        //       tree.  (We do it here because there are other well-defined
//        //       functions to perform the search.)
//        val lengthInBits = lengthInBits(key)
//
//        if (lengthInBits == 0) {
//            if (!root.isEmpty) {
//                return root
//            }
//            return null
//        }
//
//        val found = getNearestEntryForKey(key, lengthInBits)
//        if (compareKeys(key, found.key)) {
//            return found
//        }
//
//        val bitIndex = bitIndex(key, found.key)
//        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
//            val added = PatriciaTrieEntry.node<K,V>(key, null, bitIndex)
//            addEntry(added, lengthInBits)
//            incrementSize() // must increment because remove will decrement
//            val floor = previousEntry(added)
//            removeEntry(added)
//            modCount -= 2 // we didn't really modify it.
//            return floor
//        }
//        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
//            if (!root.isEmpty) {
//                return root
//            }
//            return null
//        }
//        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
//            return found
//        }
//
//        // we should have exited above.
//        throw IllegalStateException("invalid lookup: $key")
//    }
//
//    /**
//     * Goes left through the tree until it finds a valid node.
//     */
//    fun followLeft(node: PatriciaTrieEntry<K,V>): PatriciaTrieEntry<K,V> {
//        var node = node
//        while (true) {
//            var child = node.left
//            // if we hit root and it didn't have a node, go right instead.
//            if (child.isEmpty) {
//                child = node.right!!
//            }
//
//            if (child.bitIndex <= node.bitIndex) {
//                return child
//            }
//
//            node = child
//        }
//    }
//
//    /**
//     * Traverses down the right path until it finds an uplink.
//     */
//    fun followRight(node: PatriciaTrieEntry<K,V>?): PatriciaTrieEntry<K,V>? {
//        // if Trie is empty, no last entry.
//        var node = node
//        if (node?.right == null) {
//            return null
//        }
//
//        // Go as far right as possible, until we encounter an uplink.
//        while (node!!.right!!.bitIndex > node.bitIndex) {
//            node = node.right
//        }
//
//        return node.right
//    }
//
//     override fun get(key: K): V? {
//        val entry = getEntry(key)
//        return entry?.value
//    }
//
//    /**
//     * Returns the entry associated with the specified key in the
//     * PatriciaTrieBase.  Returns null if the map contains no mapping
//     * for this key.
//     *
//     *
//     * This may throw ClassCastException if the object is not of type K.
//     */
//    fun getEntry(key:K): PatriciaTrieEntry<K,V>? {
//        if (key == null) {
//            return null
//        }
//
//        val lengthInBits = lengthInBits(key)
//        val entry = getNearestEntryForKey(key, lengthInBits)
//        return if (!entry.isEmpty && compareKeys(key, entry.key)) entry else null
//    }
//
//    /**
//     * Returns the nearest entry for a given key.  This is useful
//     * for finding knowing if a given key exists (and finding the value
//     * for it), or for inserting the key.
//     *
//     * The actual get implementation. This is very similar to
//     * selectR but with the exception that it might return the
//     * root Entry even if it's empty.
//     */
//    fun getNearestEntryForKey(key: K, lengthInBits: Int): PatriciaTrieEntry<K,V> {
//        var current = root.left
//        var path = root
//        while (true) {
//            if (current.bitIndex <= path.bitIndex) {
//                return current
//            }
//
//            path = current
//            current = if (!isBitSet(key, current.bitIndex, lengthInBits)) {
//                current.left
//            } else {
//                current.right!!
//            }
//        }
//    }
//
//    /**
//     * Returns a view of this [org.apache.commons.collections4.Trie] of all elements that are prefixed
//     * by the number of bits in the given Key.
//     *
//     *
//     * The view that this returns is optimized to have a very efficient
//     * [Iterator]. The [SortedMap.firstKey],
//     * [SortedMap.lastKey] &amp; [Map.size] methods must
//     * iterate over all possible values in order to determine the results.
//     * This information is cached until the PATRICIA [org.apache.commons.collections4.Trie] changes.
//     * All other methods (except [Iterator]) must compare the given
//     * key to the prefix to ensure that it is within the range of the view.
//     * The [Iterator]'s remove method must also relocate the subtree
//     * that contains the prefixes if the entry holding the subtree is
//     * removed or changes. Changing the subtree takes O(K) time.
//     *
//     * @param key  the key to use in the search
//     * @param offsetInBits  the prefix offset
//     * @param lengthInBits  the number of significant prefix bits
//     * @return a [SortedMap] view of this [org.apache.commons.collections4.Trie] with all elements whose
//     * key is prefixed by the search key
//     */
//    private fun getPrefixMapByBits(key: K?, offsetInBits: Int, lengthInBits: Int): SortedMap<K,V> {
//        val offsetLength = offsetInBits + lengthInBits
//        require(offsetLength <= lengthInBits(key)) {
//            (offsetInBits.toString() + " + " + lengthInBits + " > " + lengthInBits(key))
//        }
//
//        if (offsetLength == 0) {
//            return this
//        }
//
//        return PrefixRangeMap(key, offsetInBits, lengthInBits)
//    }
//
//    override fun headMap(toKey: K): SortedMap<K,V> {
//        return RangeEntryMap(null, toKey)
//    }
//
//    /**
//     * Returns an entry strictly higher than the given key,
//     * or null if no such entry exists.
//     */
//    fun higherEntry(key: K): PatriciaTrieEntry<K,V>? {
//        // TODO: Cleanup so that we don't actually have to add/remove from the
//        //       tree.  (We do it here because there are other well-defined
//        //       functions to perform the search.)
//        val lengthInBits = lengthInBits(key)
//
//        if (lengthInBits == 0) {
//            if (!root.isEmpty) {
//                // If data in root, and more after -- return it.
//                if (size > 1) {
//                    return nextEntry(root)
//                }
//                // If no more after, no higher entry.
//                return null
//            }
//            // Root is empty & we want something after empty, return first.
//            return firstEntry()
//        }
//
//        val found = getNearestEntryForKey(key, lengthInBits)
//        if (compareKeys(key, found.key)) {
//            return nextEntry(found)
//        }
//
//        val bitIndex = bitIndex(key, found.key)
//        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
//            val added = TrieEntry<K,V>(key, null, bitIndex)
//            addEntry(added, lengthInBits)
//            incrementSize() // must increment because remove will decrement
//            val ceil = nextEntry(added)
//            removeEntry(added)
//            modCount -= 2 // we didn't really modify it.
//            return ceil
//        }
//        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
//            if (!root.isEmpty) {
//                return firstEntry()
//            }
//            if (size > 1) {
//                return nextEntry(firstEntry())
//            }
//            return null
//        }
//        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
//            return nextEntry(found)
//        }
//
//        // we should have exited above.
//        throw IllegalStateException("invalid lookup: $key")
//    }
//
//    /**
//     * A helper method to increment the modification counter.
//     */
//    private fun incrementModCount() {
//        ++modCount
//    }
//
//    /**
//     * A helper method to increment the [org.apache.commons.collections4.Trie] size and the modification counter.
//     */
//    fun incrementSize() {
//        size++
//        incrementModCount()
//    }
//
//    override val keys: MutableSet<K>
//        get() {
//            if (_keySet == null) {
//                _keySet = KeySet()
//            }
//            return _keySet!!
//        }
//
//    /**
//     * Returns the last entry the [org.apache.commons.collections4.Trie] is storing.
//     *
//     *
//     * This is implemented by going always to the right until
//     * we encounter a valid uplink. That uplink is the last key.
//     */
//     override fun lastEntry(): TrieEntry<K,V>? {
//        return followRight(root.left)
//    }
//
//    override fun lastKey(): K {
//        val entry = lastEntry()
//        if (entry != null) {
//            return entry.key
//        }
//        throw NoSuchElementException()
//    }
//
//    /**
//     * Returns a key-value mapping associated with the greatest key
//     * strictly less than the given key, or null if there is no such key.
//     */
//    fun lowerEntry(key: K): PatriciaTrieEntry<K,V>? {
//        // Basically:
//        // Follow the steps of adding an entry, but instead...
//        //
//        // - If we ever encounter a situation where we found an equal
//        //   key, we return it's previousEntry immediately.
//        //
//        // - If we hit root (empty or not), return null.
//        //
//        // - If we have to add a new item, we temporarily add it,
//        //   find the previousEntry to it, then remove the added item.
//        //
//        // These steps ensure that the returned value is always just before
//        // the key or null (if there was nothing before it).
//
//        // TODO: Cleanup so that we don't actually have to add/remove from the
//        //       tree.  (We do it here because there are other well-defined
//        //       functions to perform the search.)
//
//        val lengthInBits = lengthInBits(key)
//
//        if (lengthInBits == 0) {
//            return null // there can never be anything before root.
//        }
//
//        val found = getNearestEntryForKey(key, lengthInBits)
//        if (compareKeys(key, found.key)) {
//            return previousEntry(found)
//        }
//
//        val bitIndex = bitIndex(key, found.key)
//        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
//            val added = TrieEntry<K,V>(key, null, bitIndex)
//            addEntry(added, lengthInBits)
//            incrementSize() // must increment because remove will decrement
//            val prior = previousEntry(added)
//            removeEntry(added)
//            modCount -= 2 // we didn't really modify it.
//            return prior
//        }
//        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
//            return null
//        }
//        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
//            return previousEntry(found)
//        }
//
//        // we should have exited above.
//        throw IllegalStateException("invalid lookup: $key")
//    }
//
//    override fun mapIterator(): OrderedMapIterator<K,V> {
//        return TrieMapIterator()
//    }
//
//    /**
//     * Returns the entry lexicographically after the given entry.
//     * If the given entry is null, returns the first node.
//     */
//    fun nextEntry(node: PatriciaTrieEntry<K,V>?): PatriciaTrieEntry<K,V>? {
//        if (node == null) {
//            return firstEntry()
//        }
//        return nextEntryImpl(node.predecessor, node, null)
//    }
//
//    /**
//     * Scans for the next node, starting at the specified point, and using 'previous'
//     * as a hint that the last node we returned was 'previous' (so we know not to return
//     * it again).  If 'tree' is non-null, this will limit the search to the given tree.
//     *
//     * The basic premise is that each iteration can follow the following steps:
//     *
//     * 1) Scan all the way to the left.
//     * a) If we already started from this node last time, proceed to Step 2.
//     * b) If a valid uplink is found, use it.
//     * c) If the result is an empty node (root not set), break the scan.
//     * d) If we already returned the left node, break the scan.
//     *
//     * 2) Check the right.
//     * a) If we already returned the right node, proceed to Step 3.
//     * b) If it is a valid uplink, use it.
//     * c) Do Step 1 from the right node.
//     *
//     * 3) Back up through the parents until we encounter find a parent
//     * that we're not the right child of.
//     *
//     * 4) If there's no right child of that parent, the iteration is finished.
//     * Otherwise continue to Step 5.
//     *
//     * 5) Check to see if the right child is a valid uplink.
//     * a) If we already returned that child, proceed to Step 6.
//     * Otherwise, use it.
//     *
//     * 6) If the right child of the parent is the parent itself, we've
//     * already found &amp; returned the end of the Trie, so exit.
//     *
//     * 7) Do Step 1 on the parent's right child.
//     */
//    fun nextEntryImpl(
//        start: PatriciaTrieEntry<K,V>,
//        previous: PatriciaTrieEntry<K,V>?,
//        tree: PatriciaTrieEntry<K,V>?,
//    ): PatriciaTrieEntry<K,V>? {
//        var current = start
//
//        // Only look at the left if this was a recursive or
//        // the first check, otherwise we know we've already looked
//        // at the left.
//        if (previous == null || start != previous.predecessor) {
//            while (!current.left.isEmpty) {
//                // stop traversing if we've already
//                // returned the left of this node.
//                if (previous === current.left) {
//                    break
//                }
//
//                if (Companion.isValidUplink(current.left, current)) {
//                    return current.left
//                }
//
//                current = current.left
//            }
//        }
//
//        // If there's no data at all, exit.
//        if (current.isEmpty) {
//            return null
//        }
//
//        // If we've already returned the left,
//        // and the immediate right is null,
//        // there's only one entry in the Trie
//        // which is stored at the root.
//        //
//        //  / ("")   <-- root
//        //  \_/  \
//        //       null <-- 'current'
//        //
//        if (current.right == null) {
//            return null
//        }
//
//        // If nothing valid on the left, try the right.
//        if (previous != current.right) {
//            // See if it immediately is valid.
//            if (Companion.isValidUplink(current.right, current)) {
//                return current.right
//            }
//
//            // Must search on the right's side if it wasn't initially valid.
//            return nextEntryImpl(current.right!!, previous, tree)
//        }
//
//        // Neither left nor right are valid, find the first parent
//        // whose child did not come from the right & traverse it.
//        while (current === current.parent!!.right) {
//            // If we're going to traverse to above the subtree, stop.
//            if (current === tree) {
//                return null
//            }
//
//            current = current.parent!!
//        }
//
//        // If we're on the top of the subtree, we can't go any higher.
//        if (current === tree) {
//            return null
//        }
//
//        // If there's no right, the parent must be root, so we're done.
//        if (current.parent?.right == null) {
//            return null
//        }
//
//        // If the parent's right points to itself, we've found one.
//        if (previous !== current.parent?.right && isValidUplink(current.parent?.right, current.parent!!)
//        ) {
//            return current.parent?.right
//        }
//
//        // If the parent's right is itself, there can't be any more nodes.
//        if (current.parent?.right === current.parent) {
//            return null
//        }
//
//        // We need to traverse down the parent's right's path.
//        return nextEntryImpl(current.parent!!.right!!, previous, tree)
//    }
//
//    /**
//     * Returns the entry lexicographically after the given entry.
//     * If the given entry is null, returns the first node.
//     *
//     * This will traverse only within the subtree.  If the given node
//     * is not within the subtree, this will have undefined results.
//     */
//    fun nextEntryInSubtree(
//        node: TrieEntry<K,V>?,
//        parentOfSubtree: TrieEntry<K,V>?,
//    ): TrieEntry<K,V>? {
//        if (node == null) {
//            return firstEntry()
//        }
//        return nextEntryImpl(node.predecessor, node, parentOfSubtree)
//    }
//
//    override fun nextKey(key: K): K? {
//        val entry = getEntry(key)
//        if (entry != null) {
//            val nextEntry = nextEntry(entry)
//            return nextEntry?.key
//        }
//        return null
//    }
//
//    override fun prefixMap(key: K): SortedMap<K,V> {
//        return getPrefixMapByBits(key, 0, lengthInBits(key))
//    }
//
//    /**
//     * Returns the node lexicographically before the given node (or null if none).
//     *
//     * This follows four simple branches:
//     * - If the uplink that returned us was a right uplink:
//     * - If predecessor's left is a valid uplink from predecessor, return it.
//     * - Else, follow the right path from the predecessor's left.
//     * - If the uplink that returned us was a left uplink:
//     * - Loop back through parents until we encounter a node where
//     * node != node.parent.left.
//     * - If node.parent.left is uplink from node.parent:
//     * - If node.parent.left is not root, return it.
//     * - If it is root &amp; root isEmpty, return null.
//     * - If it is root &amp; root !isEmpty, return root.
//     * - If node.parent.left is not uplink from node.parent:
//     * - Follow right path for first right child from node.parent.left
//     *
//     * @param start  the start entry
//     */
//    fun previousEntry(start: PatriciaTrieEntry<K,V>): PatriciaTrieEntry<K,V>? {
//        val predecessor = start.predecessor
//        requireNotNull(predecessor) { "must have come from somewhere!" }
//
//        if (predecessor.right === start) {
//            if (Companion.isValidUplink(predecessor.left, predecessor)) {
//                return predecessor.left
//            }
//            return followRight(predecessor.left)
//        }
//        var node = predecessor
//        while (node.parent != null && node == node.parent?.left) {
//            node = node.parent!!
//        }
//
//        if (node.parent == null) { // can be null if we're looking up root.
//            return null
//        }
//
//        if (Companion.isValidUplink(node.parent?.left, node.parent!!)) {
//            if (node.parent?.left === root) {
//                if (root.isEmpty) {
//                    return null
//                }
//                return root
//            }
//            return node.parent?.left
//        }
//        return followRight(node.parent?.left)
//    }
//
//    override fun previousKey(key: K): K? {
//        val entry = getEntry(key)
//        if (entry != null) {
//            val prevEntry = previousEntry(entry)
//            return prevEntry?.key
//        }
//        return null
//    }
//
//     override fun put(key: K, value: V): V? {
//
//        val lengthInBits = lengthInBits(key)
//
//        // The only place to store a key with a length
//        // of zero bits is the root node
//        if (lengthInBits == 0) {
//            if (root.isEmpty) {
//                incrementSize()
//            } else {
//                incrementModCount()
//            }
//            return root.setKeyValue(key, value)
//        }
//
//        val found = getNearestEntryForKey(key, lengthInBits)
//        if (compareKeys(key, found.key)) {
//            if (found.isEmpty) { // <- must be the root
//                incrementSize()
//            } else {
//                incrementModCount()
//            }
//            return found.setKeyValue(key, value)
//        }
//
//        val bitIndex = bitIndex(key, found.key)
//        if (!KeyAnalyzer.isOutOfBoundsIndex(bitIndex)) {
//            if (KeyAnalyzer.isValidBitIndex(bitIndex)) { // in 99.999...9% the case
//                /* NEW KEY+VALUE TUPLE */
//                val t = TrieEntry<K,V>(key, value, bitIndex)
//                addEntry(t, lengthInBits)
//                incrementSize()
//                return null
//            }
//            if (KeyAnalyzer.isNullBitKey(bitIndex)) {
//                // A bits of the Key are zero. The only place to
//                // store such a Key is the root Node!
//
//                /* NULL BIT KEY */
//
//                if (root.isEmpty) {
//                    incrementSize()
//                } else {
//                    incrementModCount()
//                }
//                return root.setKeyValue(key, value)
//            }
//            if (KeyAnalyzer.isEqualBitKey(bitIndex) && found !== root) { // NOPMD
//                incrementModCount()
//                return found.setKeyValue(key, value)
//            }
//        }
//
//        throw IllegalArgumentException("Failed to put: $key -> $value, $bitIndex")
//    }
//
//    /**
//     * Deserializes an instance from an ObjectInputStream.
//     *
//     * @param in The source ObjectInputStream.
//     * @throws IOException            Any of the usual Input/Output related exceptions.
//     * @throws ClassNotFoundException A class of a serialized object cannot be found.
//     */
////    @Throws(
////        IOException::class,
////        java.lang.ClassNotFoundException::class
////    )  // This will fail at runtime if the stream is incorrect
////    private fun readObject(`in`: ObjectInputStream) {
////        `in`.defaultReadObject()
////        root = TrieEntry<K,V>(null, null, -1)
////        val size: Int = `in`.readInt()
////        for (i in 0..<size) {
////            val k = `in`.readObject() as K
////            val v = `in`.readObject() as V?
////            put(k, v)
////        }
////    }
//
//    /**
//     * {@inheritDoc}
//     *
//     * @throws ClassCastException if provided key is of an incompatible type
//     */
//     override fun remove(key: K): V? {
//        if (key == null) {
//            return null
//        }
//
//        val key: K = key
//        val lengthInBits = lengthInBits(key)
//        var current = root.left
//        var path = root
//        while (true) {
//            if (current.bitIndex <= path.bitIndex) {
//                if (!current.isEmpty && compareKeys(key, current.key)) {
//                    return removeEntry(current)
//                }
//                return null
//            }
//
//            path = current
//
//            current = if (!isBitSet(key, current.bitIndex, lengthInBits)) {
//                current.left
//            } else {
//                current.right!!
//            }
//        }
//    }
//
//    /**
//     * Removes a single entry from the [org.apache.commons.collections4.Trie].
//     *
//     * If we found a Key (Entry h) then figure out if it's
//     * an internal (hard to remove) or external Entry (easy
//     * to remove)
//     */
//    fun removeEntry(h: PatriciaTrieEntry<K,V>): V? {
//        if (h !== root) {
//            if (h.isInternalNode) {
//                removeInternalEntry(h)
//            } else {
//                removeExternalEntry(h)
//            }
//        }
//
//        decrementSize()
//        return h.setKeyValue(null, null)
//    }
//
//    /**
//     * Removes an external entry from the [org.apache.commons.collections4.Trie].
//     *
//     * If it's an external Entry then just remove it.
//     * This is very easy and straight forward.
//     */
//    private fun removeExternalEntry(h: PatriciaTrieEntry<K,V>) {
//        require(h !== root) { "Cannot delete root Entry!" }
//        require(h.isExternalNode) { "$h is not an external Entry!" }
//
//        val child= (if (h.left === h) h.right else h.left)!!
//
//        val parent = h.parent!!
//
//        if (parent.left === h) {
//            parent.left = child
//        } else {
//            parent.right = child
//        }
//
//        // either the parent is changing, or the predecessor is changing.
//        if (child.bitIndex > parent.bitIndex) {
//            child.parent = parent
//        } else {
//            child.predecessor = parent
//        }
//    }
//
//    /**
//     * Removes an internal entry from the [org.apache.commons.collections4.Trie].
//     *
//     * If it's an internal Entry then "good luck" with understanding
//     * this code. The Idea is essentially that Entry p takes Entry h's
//     * place in the trie which requires some re-wiring.
//     */
//    private fun removeInternalEntry(h: PatriciaTrieEntry<K,V>) {
//        require(h !== root) { "Cannot delete root Entry!" }
//        require(h.isInternalNode) { "$h is not an internal Entry!" }
//
//        val p = h.predecessor
//
//        // Set P's bitIndex
//        p.bitIndex = h.bitIndex
//
//        // Fix P's parent, predecessor and child Nodes
//        run {
//            val child= (if (p.left === h) p.right else p.left)!!
//
//            // if it was looping to itself previously,
//            // it will now be pointed from its parent
//            // (if we aren't removing its parent --
//            //  in that case, it remains looping to itself).
//            // otherwise, it will continue to have the same
//            // predecessor.
//            if (p.predecessor === p && p.parent !== h) {
//                p.predecessor = p.parent!!
//            }
//
//            val parent = p.parent!!
//
//            if (parent.left === p) {
//                parent.left = child
//            } else {
//                parent.right = child
//            }
//            if (child.bitIndex > parent.bitIndex) {
//                child.parent = parent
//            }
//        }
//
//        // Fix H's parent and child Nodes
//        run {
//            // If H is a parent of its left and right child
//            // then change them to P
//            if (h.left.parent === h) {
//                h.left.parent = p
//            }
//
//            if (h.right?.parent === h) {
//                h.right?.parent = p
//            }
//
//            // Change H's parent
//            if (h.parent?.left === h) {
//                h.parent?.left = p
//            } else {
//                h.parent?.right = p
//            }
//        }
//
//        // Copy the remaining fields from H to P
//        //p.bitIndex = h.bitIndex;
//        p.parent = h.parent
//        p.left = h.left
//        p.right = h.right
//
//        // Make sure that if h was pointing to any uplinks,
//        // p now points to them.
//        if (Companion.isValidUplink(p.left, p)) {
//            p.left.predecessor = p
//        }
//
//        if (Companion.isValidUplink(p.right, p)) {
//            p.right?.predecessor = p
//        }
//    }
//
//    /**
//     * Returns the [java.util.BasicEntry] whose key is closest in a bitwise XOR
//     * metric to the given key. This is NOT lexicographic closeness.
//     * For example, given the keys:
//     *
//     *
//     *  1. D = 1000100
//     *  1. H = 1001000
//     *  1. L = 1001100
//     *
//     *
//     * If the [org.apache.commons.collections4.Trie] contained 'H' and 'L', a lookup of 'D' would
//     * return 'L', because the XOR distance between D &amp; L is smaller
//     * than the XOR distance between D &amp; H.
//     *
//     * @param key  the key to use in the search
//     * @return the [java.util.BasicEntry] whose key is closest in a bitwise XOR metric
//     * to the provided key
//     */
//    fun select(key: K): PatriciaTrieEntry<K,V>? {
//        val lengthInBits = lengthInBits(key)
//        val reference = Reference<PatriciaTrieEntry<K,V>?>()
//        if (!selectR(root.left, -1, key, lengthInBits, reference)) {
//            return reference.get()
//        }
//        return null
//    }
//
//    /**
//     * Returns the key that is closest in a bitwise XOR metric to the
//     * provided key. This is NOT lexicographic closeness!
//     *
//     * For example, given the keys:
//     *
//     *
//     *  1. D = 1000100
//     *  1. H = 1001000
//     *  1. L = 1001100
//     *
//     *
//     * If the [org.apache.commons.collections4.Trie] contained 'H' and 'L', a lookup of 'D' would
//     * return 'L', because the XOR distance between D &amp; L is smaller
//     * than the XOR distance between D &amp; H.
//     *
//     * @param key  the key to use in the search
//     * @return the key that is closest in a bitwise XOR metric to the provided key
//     */
//    fun selectKey(key: K): K? {
//        val entry = select(key)
//        if (entry == null) {
//            return null
//        }
//        return entry.key
//    }
//
//    private fun selectR(
//        h: PatriciaTrieEntry<K,V>, bitIndex: Int,
//        key: K, lengthInBits: Int,
//        reference: Reference<PatriciaTrieEntry<K,V>?>,
//    ): Boolean {
//        if (h.bitIndex <= bitIndex) {
//            // If we hit the root Node and it is empty
//            // we have to look for an alternative best
//            // matching node.
//            if (!h.isEmpty) {
//                reference.set(h)
//                return false
//            }
//            return true
//        }
//
//        if (!isBitSet(key, h.bitIndex, lengthInBits)) {
//            if (selectR(h.left, h.bitIndex, key, lengthInBits, reference)) {
//                return selectR(h.right!!, h.bitIndex, key, lengthInBits, reference)
//            }
//        } else if (selectR(h.right!!, h.bitIndex, key, lengthInBits, reference)) {
//            return selectR(h.left, h.bitIndex, key, lengthInBits, reference)
//        }
//        return false
//    }
//
//    /**
//     * Returns the value whose key is closest in a bitwise XOR metric to
//     * the provided key. This is NOT lexicographic closeness!
//     *
//     * For example, given the keys:
//     *
//     *
//     *  1. D = 1000100
//     *  1. H = 1001000
//     *  1. L = 1001100
//     *
//     *
//     * If the [org.apache.commons.collections4.Trie] contained 'H' and 'L', a lookup of 'D' would
//     * return 'L', because the XOR distance between D &amp; L is smaller
//     * than the XOR distance between D &amp; H.
//     *
//     * @param key  the key to use in the search
//     * @return the value whose key is closest in a bitwise XOR metric
//     * to the provided key
//     */
//    fun selectValue(key: K): V? {
//        val entry = select(key)
//        if (entry == null) {
//            return null
//        }
//        return entry.value
//    }
//
//
////     override fun size(): Int {
////        return size
////    }
//
//    override fun subMap(fromKey: K, toKey: K): SortedMap<K,V> {
//        return RangeEntryMap(fromKey, toKey)
//    }
//
//    /**
//     * Finds the subtree that contains the prefix.
//     *
//     * This is very similar to getR but with the difference that
//     * we stop the lookup if h.bitIndex > lengthInBits.
//     */
//    fun subtree(prefix: K?, offsetInBits: Int, lengthInBits: Int): PatriciaTrieEntry<K,V>? {
//        var current = root.left
//        var path = root
//        while (true) {
//            if (current.bitIndex <= path.bitIndex || lengthInBits <= current.bitIndex) {
//                break
//            }
//
//            path = current
//            current = if (!isBitSet(prefix, offsetInBits + current.bitIndex, offsetInBits + lengthInBits)) {
//                current.left
//            } else {
//                current.right!!
//            }
//        }
//
//        // Make sure the entry is valid for a subtree.
//        val entry = if (current.isEmpty) path else current
//
//        // If entry is root, it can't be empty.
//        if (entry.isEmpty) {
//            return null
//        }
//
//        val endIndexInBits = offsetInBits + lengthInBits
//
//        // if root && length of root is less than length of lookup,
//        // there's nothing.
//        // (this prevents returning the whole subtree if root has an empty
//        //  string and we want to lookup things with "\0")
//        if (entry === root && lengthInBits(entry.key) < endIndexInBits) {
//            return null
//        }
//
//        // Found key's length-th bit differs from our key
//        // which means it cannot be the prefix...
//        if (isBitSet(prefix, endIndexInBits - 1, endIndexInBits)
//            != isBitSet(entry.key, lengthInBits - 1, lengthInBits(entry.key))
//        ) {
//            return null
//        }
//
//        // ... or there are less than 'length' equal bits
//        val bitIndex = keyAnalyzer.bitIndex(
//            prefix, offsetInBits, lengthInBits,
//            entry.key, 0, lengthInBits(entry.key)
//        )
//
//        if (bitIndex >= 0 && bitIndex < lengthInBits) {
//            return null
//        }
//
//        return entry
//    }
//
//    override fun tailMap(fromKey: K): SortedMap<K,V> {
//        return RangeEntryMap(fromKey, null)
//    }
//
//
//    override val values: MutableCollection<V>
//        get() {
//            if (_values == null) {
//                _values = Values()
//            }
//            return _values!!
//        }
//
//    /**
//     * Serializes this object to an ObjectOutputStream.
//     *
//     * @param out the target ObjectOutputStream.
//     * @throws IOException thrown when an I/O errors occur writing to the target stream.
//     */
////    @Throws(IOException::class)
////    private fun writeObject(out: ObjectOutputStream) {
////        out.defaultWriteObject()
////        out.writeInt(this.size())
////        for (entry in entrySet()!!) {
////            out.writeObject(entry.getKey())
////            out.writeObject(entry.getValue())
////        }
////    }
//
//    companion object {
//
//        /**
//         * Returns true if 'next' is a valid uplink coming from 'from'.
//         */
//        fun isValidUplink(next: PatriciaTrieEntry<*, *>?, from: PatriciaTrieEntry<*, *>): Boolean {
//            return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty
//        }
//    }
//}
